|
A primality test is an algorithm for determining whether an input number is prime. Amongst other fields of mathematics, it is used for cryptography. Unlike integer factorization, primality tests do not generally give prime factors, only stating whether the input number is prime or not. Factorization is thought to be a computationally difficult problem, whereas primality testing is comparatively easy (its running time is polynomial in the size of the input). Some primality tests ''prove'' that a number is prime, while others like Miller–Rabin prove that a number is composite. Therefore, the latter might be called ''compositeness tests'' instead of primality tests. ==Simple methods== The simplest primality test is ''trial division'': Given an input number ''n'', check whether any prime integer ''m'' from 2 to evenly divides ''n'' (the division leaves no remainder). If ''n'' is divisible by any ''m'' then ''n'' is composite, otherwise it is prime.〔Riesel (1994) pp.2-3〕 For example, to test whether 17 is prime, test whether 17 is divisible by 2, or 3. Since a prime is only divisible by 1 and itself, if we reach 3 without finding a divisor, then we have proven that 17 is prime. However, we don't actually have to check all numbers up to ''n''. Let's look at another example: all the divisors of 100: :2, 4, 5, 10, 20, 25, 50 here we see that the largest factor is 100/2 = 50. This is true for all ''n'': all divisors are less than or equal to ''n''/2. We can do better though. If we take a closer look at the divisors, we will see that some of them are redundant. If we write the list differently: :100 = 2 × 50 = 4 × 25 = 5 × 20 = 10 × 10 = 20 × 5 = 25 × 4 = 50 × 2 it becomes obvious. Once we reach 10, which is , the divisors just flip around and repeat. Therefore, we can further eliminate testing divisors greater than .〔 We can also eliminate all the even numbers greater than 2, since if an even number can divide ''n'', so can 2. The algorithm can be improved further by observing that all primes are of the form 6''k'' ± 1, with the exception of 2 and 3. This is because all integers can be expressed as (6''k'' + ''i'') for some integer ''k'' and for ''i'' = −1, 0, 1, 2, 3, or 4; 2 divides (6''k'' + 0), (6''k'' + 2), (6''k'' + 4); and 3 divides (6''k'' + 3). So a more efficient method is to test if ''n'' is divisible by 2 or 3, then to check through all the numbers of form 6''k'' ± 1 . This is 3 times as fast as testing all ''m''. Generalising further, it can be seen that all primes are of the form ''c''#''k'' + ''i'' for ''i'' < ''c''# where ''i'' represents the numbers that are coprime to c# and where ''c'' and ''k'' are integers. For example, let ''c'' = 6. Then ''c''# = 2 3 5 = 30. All integers are of the form 30''k'' + ''i'' for ''i'' = 0, 1, 2,...,29 and ''k'' an integer. However, 2 divides 0, 2, 4,...,28 and 3 divides 0, 3, 6,...,27 and 5 divides 0, 5, 10,...,25. So all prime numbers are of the form 30''k'' + ''i'' for ''i'' = -1, 1, 7, 11, 13, 17, 19, 23, 29 (i.e. for ''i'' < 30 such that gcd(''i'',30) = 1). Note that if ''i'' and 30 are not coprime, then 30''k'' + ''i'' is divisible by a prime divisor of 30, namely 2, 3 or 5, and is therefore not prime. As ''c'' → ∞, the number of values that ''c''#''k'' + ''i'' can take over a certain range decreases, and so the time to test ''n'' decreases. For this method, it is also necessary to check for divisibility by all primes that are less than ''c''. Observations analogous to the preceding can be applied recursively, giving the Sieve of Eratosthenes. A good way to speed up these methods (and all the others mentioned below) is to pre-compute and store a list of all primes up to a certain bound, say all primes up to 200. (Such a list can be computed with the Sieve of Eratosthenes or by an algorithm that tests each incremental ''m'' against all known primes < ). Then, before testing ''n'' for primality with a serious method, ''n'' can first be checked for divisibility by any prime from the list. If it is divisible by any of those numbers then it is composite, and any further tests can be skipped. A simple, but very inefficient primality test uses Wilson's theorem, which states that ''p'' is prime if and only if: : Although this method requires about ''p'' modular multiplications, rendering it impractical, theorems about primes and modular residues form the basis of many more practical methods. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Primality test」の詳細全文を読む スポンサード リンク
|